#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

struct node{
    int data;   // 假定数据域，都是整数
    node* next; // 指针域，指向下一个结点的指针
};

struct LinkedStack {
    node* head;     // 头指针（指向首元节点）
    void init() { head = nullptr; }
    void push(int e) {
        node* newNode = new node;
        newNode->data = e;
        // 把 newNode 加入链表的头部（栈顶）
        newNode->next = head;
        head = newNode;
    } 
    bool pop(int &e) {
        if(head == nullptr) return false;
        e = head->data;
        node* delNode = head;   // 准备删除的首元结点
        head = delNode->next;   // 重新设置 head 指针
        delete delNode;         // 释放 delNode 结点的空间
        return true;
    }
    void print(){
        node* p = head;     // p 的初始值为首元节点的指针
        while(p){
            cout << p->data << ", ";
            p = p->next;
        }
        cout << "\n";
    }
};

int main(){
    LinkedStack myStack;
    int startTime = clock();
    for(int i = 0; i < 100000; i++){
        myStack.init();
        for(int j = 0; j < 10000; j++)
            myStack.push(j);
        int ele;
        for(int j = 0; j < 10000; j++)
            myStack.pop(ele);
    }
    int endTime = clock();
    double time = double(endTime-startTime)/CLOCKS_PER_SEC;
    cout << "10000 times 10000 push and 10000 pop: " << time << "s\n"; 
}